package bbc;

import java.util.ArrayList;

public class akus {
}


/**
 * 作者： 马中华   https://blog.csdn.net/zhongqi2513
 * 时间： 2019/6/20 10:33
 * 描述：
 *      求出一个一维数组的蓄水数。数组中的每个位置上的值，就是高度，
 *      如果某个值的左右两边都有比它高的值，那么这个位置就可以蓄水。
 *      蓄水的容量 = max(左边， 右边) - 当前位置的值
 */
 class WaterArray01 {

    public static void main(String[] args) {

        //   能蓄水的位置和值：        0,1,2,0,0,2,2,0
        int[] waterArray1 = new int[]{4,3,2,1,3,0,5,0,1};
        ArrayList<Integer> result1 = findTotalWaterStorage(waterArray1);
        System.out.println("蓄水总量为：" + result1.toString());

        //   能蓄水的位置和值：        0,0,0,3,4,1,4,0,1,2,0,0
        int[] waterArray2 = new int[]{2,1,5,2,1,4,1,7,2,1,3,1};
        ArrayList<Integer> result2 = findTotalWaterStorage(waterArray2);
        System.out.println("蓄水总量为：" + result2.toString());

        //   能蓄水的位置和值：        0,0,0,3,4,1,4,0,1,2,0,0
        int[] waterArray3 = new int[]{4,1,3,5,3,6,2,1,4,7,2,6,4};
        ArrayList<Integer> result3 = findTotalWaterStorage(waterArray3);
        System.out.println("蓄水总量为：" + result3.toString());
    }

    /**
     * 整体思路：
     *  先找到最高点，然后分别从左，和 从右 往这个高点遍历。算出蓄水数
     */
    private static ArrayList<Integer> findTotalWaterStorage(int[] waterArray) {

        int totalWater = 0;

        // 最高点的值
        int maxHeight = waterArray[0];
        // 最高点的位置
        int maxHeightIndex = 0;

        // 找出最高点的位置和值
        for(int i = 1; i<waterArray.length; i++){
            if(maxHeight < waterArray[i]){
                maxHeight = waterArray[i];
                maxHeightIndex = i;
            }
        }

        /**
         * 隐性前提： leftHeight  一定小于或者等于  maxHeight
         * 隐性前提： rightHeight 一定小于或者等于  maxHeight
         */
        ArrayList<Integer> res = new ArrayList<>();
        // 从左往右扫描
        int leftHeight = waterArray[0];
        for(int i=1; i<maxHeightIndex; i++){
            // 如果当前遍历的位置是低谷
            if(waterArray[i] < leftHeight){
                res.add (leftHeight - waterArray[i]);
            }else{
                res.add(0);
                // 如果不是低谷，则更换左边的较高位置
                leftHeight = waterArray[i];
            }
        }

        // 从右往左
        int rightHeight = waterArray[waterArray.length-1];
        for(int i=waterArray.length-2; i>maxHeightIndex; i--){
            // 如果当前遍历的位置是低谷
            if(waterArray[i] < rightHeight){
                res.add(rightHeight - waterArray[i]);
            }else{

                res.add(0);
                // 如果不是低谷，则更换左边的较高位置
                rightHeight = waterArray[i];
            }
        }
        return res;
    }
}